package algorithm.t202111;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/24 9:35
 * @description :6道
 * 明天论文开题报告，真快啊真快啊，一年前这个时候我在准备6级考试。手机系统坏了，更新的时候，希望手机能整好。
 * persevere to last
 * 2021.11.24
 * 李红磊
 * 2021年11月24日21:21:15
 */
public class t20211124 {

    //423.从英文中重建数字
    String[] arr = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    int[] priority = new int[]{0, 8, 6, 3, 5, 7, 2, 4, 1, 9};

    public String originalDigits(String s) {
        int[] pi = new int[26];
        for (int i = 0; i < s.length(); i++) pi[s.charAt(i) - 'a']++;

        StringBuffer buffer = new StringBuffer();

        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char item : arr[i].toCharArray()) k = Math.min(k, pi[item - 'a']);
            for (char element : arr[i].toCharArray()) pi[element - 'a'] -= k;
            while (k-- > 0) buffer.append(i);
        }
        char[] toCharArray = buffer.toString().toCharArray();
        Arrays.sort(toCharArray);
        return new String(toCharArray);
    }

    //1137.第N个泰波那契数
    public int tribonacci(int n) {
        return 0;
    }

    //面试题16.18 模式匹配
    public boolean patternMatching(String pattern, String value) {
        if (pattern.equals("a") || pattern.equals("b")) return true;

        if (pattern.length() == 0) return value.length() == 0;

        //value为空时，判断pattern是否只有a或b
        if (value.length() == 0) {
            boolean aExist = false;
            boolean bExist = false;
            for (int i = 0; i < pattern.length(); i++) {
                if (pattern.charAt(i) == 'a') aExist = true;
                else if (pattern.charAt(i) == 'b') bExist = true;


            }
            if (aExist && bExist) return false;

            return true;

        }
        int a_count = 0, b_count = 0;
        for (char c : pattern.toCharArray()) {
            if (c == 'a') a_count++;
            else if (c == 'b') b_count++;
        }

        int value_len = value.length();
        //若a_count或b_count其中有一项为0，则判断value是否可以被等分
        if (a_count * b_count == 0) {
            int count = a_count + b_count;
            if (value_len % count != 0) return false;
            else {
                int len = value_len / count;
                for (int i = len; i < value_len; i += len) {
                    if (!stringEqual(value.toCharArray(), 0, i, len)) return false;
                }
            }
            return true;
        }

        //value不为空，acount和bcount也都不为空，那么就开始枚举所有可能
        for (int i = 0; i <= value_len; i++) {//i表示a对应字符串的长度
            if (value_len - i * a_count < 0) break;

            int lenB = (value_len - i * a_count) / b_count;

            //lenB表示b对应字符串的长度
            //需要满足条件才进行判断
            if (lenB * b_count + i * a_count == value_len) {
                int idx = 0;
                int[] ab = new int[2];
                ab[0] = -1;
                ab[1] = -1;

                boolean notMatch = false;

                for (char item : pattern.toCharArray()) {
                    if (item == 'a') {
                        if (ab[0] == -1) ab[0] = idx;
                        else {
                            // 每次为a都和初始的字符串比较
                            if (!stringEqual(value.toCharArray(), ab[0], idx, i)) {
                                notMatch = true;
                                break;
                            }
                        }
                        idx += i;

                    } else {
                        if (ab[1] == -1) ab[1] = idx;

                        else {
                            if (!stringEqual(value.toCharArray(), ab[1], idx, lenB)) {
                                notMatch = true;
                                break;
                            }
                        }
                        idx += lenB;

                    }
                    //判断a和b是否相等
                    if (lenB == i) {
                        if (ab[0] != -1 && ab[1] != -1) {
                            if (stringEqual(value.toCharArray(), ab[0], ab[1], lenB)) {
                                notMatch = true;
                                break;
                            }
                        }
                    }

                }
                // notMatch为false说明之前的几个判断里面都不是因为break跳出
                if (!notMatch) {
                    return true;
                }


            }
        }
        return false;
    }

    private boolean stringEqual(char[] toCharArray, int i, int j, int len) {
        for (int k = 0; k < len; k++) {
            if (toCharArray[k + i] != toCharArray[k + j]) return false;
        }
        return true;
    }

    //2.两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int k = l2 == null ? 0 : l2.val;
            int sum = x + k + carry;

            carry = sum / 10;
            sum = sum % 10;

            cur.next = new ListNode(sum);
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
            cur = cur.next;

        }

        if (carry == 1) cur.next = new ListNode(carry);
        return dummy.next;

    }

    //4.寻找两个正序数组的中位数
    PriorityQueue<Integer> bigHeap, smallHeap;
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        bigHeap = new PriorityQueue<>((x, y) -> y - x);
        smallHeap = new PriorityQueue<>();

        int len1 = nums1.length, len2 = nums2.length;

        int[] arr = new int[len1 + len2];

        for (int i = 0; i < len1; i++) {
            arr[i] = nums1[i];
        }
        for (int i = len1; i < arr.length; i++) {
            arr[i] = nums2[i - len1];
        }
        Arrays.sort(arr);

        for (int i = 0; i < arr.length; i++) {
            if (smallHeap.size() != bigHeap.size()) {
                smallHeap.add(arr[i]);
                bigHeap.add(smallHeap.poll());

            } else {
                bigHeap.add(arr[i]);
                smallHeap.add(bigHeap.poll());
            }
        }

        return smallHeap.size() == bigHeap.size() ? (smallHeap.poll() + bigHeap.poll()) / 2.0 : smallHeap.poll();

    }

    //48.旋转图像
    public void rotate(int[][] matrix) {
        if (matrix == null) return;
        int rows = matrix.length, columns = matrix[0].length;

        int[][] tem = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                tem[j][rows - 1 - i] = matrix[i][j];
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                matrix[i][j] = tem[i][j];
            }
        }

    }


    public static void main(String[] args) {
        t20211124 t20211124 = new t20211124();
        /*ListNode head1 = new ListNode(2);
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(9);
        head1.next = node1;
        node1.next = node2;

        ListNode head2 = new ListNode(5);
        ListNode node3 = new ListNode(6);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(9);
        head2.next = node3;
        node3.next = node4;
        node4.next = node5;

        System.out.println(t20211124.addTwoNumbers(head1, head2));*/
        System.out.println(t20211124.findMedianSortedArrays(new int[]{1, 2}, new int[]{3}));

    }
}
